package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _113_pathSum {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, path, res);
        // 2. 找到所有路径的路径和等于目标值的路径
        List<List<Integer>> ans = new ArrayList<>();
        for (List<Integer> onePath : res) {
            int sum = 0;
            for (int val : onePath) {sum += val;}
            if (sum == targetSum) {ans.add(onePath);}
        }

        return ans;
    }
    private void dfs(TreeNode node,
                     List<Integer> path,
                     List<List<Integer>> res) {
        if (node == null) {return;}
        path.add(node.val);
        if (node.left == null && node.right == null) {
            // 添加路径的时候需要 new 一个新的 ArrayList 的原因：
            // 1. 使得 res 中的对象和 path 不是同一个对象
            res.add(new ArrayList<>(path));
        }
        dfs(node.left, path, res);
        dfs(node.right, path, res);
        // 回溯的过程中，将当前的节点从 path 中删除
        path.remove(path.size() - 1);
    }



    public List<List<Integer>> pathSum1(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        dfs1(root, target, new ArrayList<>(), res);
        return res;
    }

    private void dfs1(TreeNode node, int targetSum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) {return;}
        path.add(node.val);
        int currNodeTarget = targetSum - node.val;
        if (node.left == null && node.right == null && currNodeTarget == 0) {
            // 添加路径的时候需要 new 一个新的 ArrayList 的原因：
            // 1. 使得 res 中的对象和 path 不是同一个对象
            res.add(new ArrayList<>(path));
        }
        dfs1(node.left, currNodeTarget, path, res);
        dfs1(node.right, currNodeTarget, path, res);
        // 回溯的过程中，将当前的节点从 path 中删除
        path.remove(path.size() - 1);
    }
}
